Listing 1 - 10 of 69 << page
of 7
>>
Sort by

Dissertation
An ant-based approach for solving dynamic constraint optimization problems
Authors: ---
ISBN: 9056827472 Year: 2006 Publisher: Leuven Katholieke Universiteit Leuven

Loading...
Export citation

Choose an application

Bookmark

Abstract

Constraint optimalisatie problemen worden in een groot aantal industriele toepassingen gebruikt. De vleugels van een vliegtuig ontwerpen, een personeelsrooster voor een spoorwegmaatschappij opstellen en de frequenties voor de masten van mobiele telefoons bepalen zijn allemaal voorbeelden van constraint optimalisatie problemen. Bovendien veranderen de meeste praktische problemen voortdurend: spoorwegbeambten worden ziek, gebruikers van mobiele telefoons verplaatsen zich van de ene mast naar de andere. Het ontwerpen van een vliegtuigvleugel is zo een complexe taak dat er tijdens het ontwerp zelf voortdurend nieuwe vereisten worden geintroduceerd. In deze tekst ontwikkelen we een nieuw algoritme om dynamische constraint optimalisatie problemen op te lossen. Het Dynamic Constraint Optimization Ant Algorithm (DynCOAA) is een mieren-gebaseerd algoritme, dat vanaf het begin ontworpen werd om dynamische problemen op te lossen. Door mieren-gebaseerde informatie-verzameltechnieken te gebruiken kan de verzamelde informatie snel en effectief herbruikt worden nadat een aanpassing aan het probleem gebeurd is. We stellen zowel een gecentraliseerd als een gedistribueerd algoritme. In beide algoritmen is een modulair ontwerp met een duidelijke scheiding van verantwoordelijkheden tussen de entiteiten zeer belangrijk. Dit resulteert in een flexibel algoritme, dat gemakkelijk aangepast kan worden wanneer extra functionaliteit zoals load balancing of het dynamisch ontdekken van domeinkennis nodig is. We evalueren DynCOAA door het te vergelijken met drie andere algoritmen. Eerst vergelijken we de resultaten van een breed scala van artificiele problemen. Hierdoor kunnen we de problemen categoriseren en de eigenschappen identificeren van de problemen waarvoor DynCOAA het beste presteert. Ten slotte vergelijken we DynCOAA met de andere algoritmen in een levensechte toepassing. De conclusie is dat de eigenschappen waar DynCOAA geschikt voor is ook voorkomen in levensechte problemen. Constraint optimization problems are used in a large number of industrial applications. Computing the optimal layout for a manufacturing plant, designing the wing of an airplane, computing the ideal crew roster for an railroad company and assigning frequencies to the antennae of cellular networks are all examples of constraint optimization problems. Moreover, most practical problems change constantly: manufacturing plants have to fit in new designs, railroad workers can get sick and cellphone users drive from one antenna to another. The design of an airplane wing itself is such a complicated task that during the design phase, new requirements are introduced all the time. In this dissertation, we develop a new algorithm for solving dynamic constraint optimization problems. The Dynamic Constraint Optimization Ant Algorithm (DynCOAA) is an ant-based algorithm, that is designed from the beginning to solve dynamic problems. The use of ant-based information gathering techniques allows for a fast and effective reuse of information after changes to the problem have occurred. We present both a centralized and a distributed algorithm. In both algorithms, a modular design with a clear separation of concerns between the entities is very important. This results in a flexible algorithm, that can be easily adapted to incorporate additional requirements such as load balancing and the dynamic discovery of domain knowledge. The DynCOAA algorithm is evaluated by comparing its performance to the performance of three different algorithms. By comparing the results of a broad range of artificial problems, we are able to categorise the problems and to identify the characteristics of those problems for which DynCOAA is the best performing algorithm. Finally, we compare DynCOAA to the other algorithms in a real-world application. We conclude that the characteristics we identified in the artificial problems also occur in real-world problems. Constraint optimalisatie problemen worden zeer vaak gebruikt in industriele toepassingen. Treinregelingen, de layout van fabriekshallen, de weg die de postboden moeten volgen, het zijn allemaal toepassingen van constraint optimalisatie problemen. In deze thesis ontwikkelen we een nieuw algoritme (het DynCOAA algoritme) om zulke problemen op te lossen. We focussen ons daarbij op de dynamische versie van deze problemen: als er iets verandert aan het probleem, moet er snel een lichtjes gewijzigde oplossing berekend worden. Bijvoorbeeld, als er ergens een trein vertraging oploopt, moet er zo snel mogelijk een nieuwe regeling uitgewerkt worden. Het algoritme dat we ontwikkeld hebben is gebaseerd op biologische fenomenen: het gedrag van mieren. Een groep van mieren is zeer goed in staat om, zonder dat de mieren rechtstraaks met elkaar praten, de korste weg te zoeken van het mierennest naar een voedselbron. Dezelfde mechanismen die mieren gebruiken om hun acties te coordineren gebruiken wij in ons algoritme om een goede oplossing voor de gestelde problemen te vinden. Uit ons onderzoek blijkt dat het mieren-gebaseerde algoritme voor een aantal problemen beter presteert als andere, traditionele algoritmen. Dit is voornamelijk het geval bij problemen die gestructureerd zijn en die snel veranderen, zonder dat deze veranderingen zeer groot zijn. Bovendien tonen we aan dat deze eigenschappen wel degelijk voorkomen bij levensechte problemen.

Listing 1 - 10 of 69 << page
of 7
>>
Sort by


Copyright ©2024 SemperTool